This disclosure relates to the field of computer systems and data storage. More particularly, a system, method, and apparatus are provided for performing concurrent updates on variable-length data that has been indexed and sequentially stored in a manner that facilitates reverse reading of the data.
Variable-length data are stored in many types of applications and computing environments. For example, events that occur on a computer system, perhaps during execution of a particular application, are often logged and stored sequentially (e.g., according to timestamps indicating when they occurred) in log files, log-structured databases, and/or other repositories. Because different information is typically recorded for different events (e.g., different system metrics or application metrics), the records often have varying lengths.
When reading the recorded data in the same order it was written, it is relatively easy to quickly navigate the data and proceed from one record to the next, to find a requested record or for some other purpose. However, when attempting to scan the data in reverse order (e.g., to find the most recent record of a particular type or matching specified criteria), the task is more difficult because the storage schemes typically are not designed to support reverse navigation or scanning.
In addition, one or more set operations (e.g., union, intersection, difference) on variable-length data that has been stored and indexed to facilitate reverse reading may be required in order to efficiently satisfy complex queries. Because the data are formatted for reverse reading, typical methods of searching for and aggregating particular data (e.g., data records that have specified values for multiple key fields) will not be efficient and may not be useful. Traditional key/value databases have not supported such operations, which prevents them from supporting some complex queries.
Further, multiple queries may target the data at the same time, possibly in the midst of write operations that change the data and/or add new data. To ensure accurate results for these operation, and/or to avoid locking the data, it may be preferable for each query to be executed against a copy or version of the data as it existed at the time of the query (e.g., to avoid tainting the data with the effect of write operations conducted after the query was received or initiated). However, making separate copies of stored data for different queries would be prohibitively expensive.
Yet further, it may be necessary to perform concurrent updates to the data, especially in environments in which the data are received from multiple sources or inputs. Even during periods of frequent updates, however, it may be desirable to ensure each update is performed atomically (e.g., an entire write operation is applied contiguously), and it may be desirable to minimize locking of the data during such updates.